#力扣30 串联所有单词的子串

from collections import defaultdict, Counter
from typing import List


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not words or not s:
            return []

        word_counts = Counter(words)
        m = len(words)
        word_len = len(words[0])
        total_len = m * word_len
        s_len = len(s)
        result = []

        if s_len < total_len:
            return []

        for i in range(word_len):
            left = i
            current_counts = defaultdict(int)
            for right in range(i, s_len, word_len):
                current_word = s[right: right + word_len]
                current_counts[current_word] += 1

                # 当窗口中的单词数超过m时，移动左指针
                while (right - left) // word_len + 1 > m:
                    left_word = s[left: left + word_len]
                    current_counts[left_word] -= 1
                    if current_counts[left_word] == 0:
                        del current_counts[left_word]
                    left += word_len

                # 检查窗口中的单词数是否等于m，并比较计数
                if (right - left) // word_len + 1 == m:
                    if current_counts == word_counts:
                        result.append(left)

        return result